import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: 23735
 * Date: 2023-01-14
 * Time: 23:39
 */
public class Solution {
//     思路:
//     排序 + 双(三)指针
//     排过序之后, 三个指针, 分别确定 前中后三个数
//     第一个数, 使用一个循环,
//     第二三个数, mid=left+1, right=len - 1;
//     注意 如果某个数出现了重复  直接跳过
//     三数之和 ==0记录到结果,  <0,mid++,  >0,right--
    public List<List<Integer>> threeSum(int[] nums) {
        List<List<Integer>> lists=new ArrayList<>();
        Arrays.sort(nums);
        int len=nums.length;
        for(int left=0;left<len-2;left++){
            if(left>0&&nums[left]==nums[left-1]){
                continue;
            }
            int mid=left+1;
            int right=len-1;
            while(mid<right){
                // 下面这两个 if 要一个就够了
                // 因为目的是为了 防止出现重复
                // 如果 三数之和为0 那么mid++的同时,right--
                // 只需要考虑三数之和为0 的情况即可,其他情况不会影响结果
                // 两个都发生了变化,所以只要保证其中一个不重复即可
                if(mid-1>left&&nums[mid]==nums[mid-1]){
                    // mid-1>left 是因为第一第二个数可以相同
                    mid++;
                    continue;
                }
                // if(right<len-1&&nums[right]==nums[right+1]){
                //     right--;
                //     continue;
                // }
                int temp=nums[left]+nums[mid]+nums[right];
                if(temp==0){
                    List<Integer> list=new ArrayList<>();
                    list.add(nums[left]);
                    list.add(nums[mid]);
                    list.add(nums[right]);
                    lists.add(list);
                    mid++;
                    right--;
                }else if(temp<0){
                    // 结果偏小
                    mid++;
                }else{
                    // 结果偏大
                    right--;
                }
            }
        }
        return lists;
    }
}
